package josephu

import (
	"fmt"
)

type Boy struct {
	No   int  // 编号
	Next *Boy // 指向下一个小孩
}

/*
*
编写一个函数，构成单向的环形链表
num：个数
*Boy: 返回该环形的链表的第一个小孩的指针，为了方便后续遍历
*/
func AddBody(num int) *Boy {
	first := &Boy{}  // 空节点
	curBoy := &Boy{} // 空节点

	if num < 1 {
		fmt.Println("传入的参数不合理")
		return first
	}

	for i := 1; i <= num; i++ {
		boy := &Boy{
			No: i,
		}
		if i == 1 { // 第一个小孩，需要特殊处理
			first = boy // 不要动
			curBoy = boy
			curBoy.Next = first // 构成环形链表
		} else {
			curBoy.Next = boy
			curBoy = boy
			curBoy.Next = first // 构成环形链表
		}
	}

	return first
}

// 显示单向环形列表
func ShowBoy(first *Boy) {
	if first.Next == nil {
		fmt.Println("链表为空，没有小孩...")
		return
	}
	// 创建一个指针，帮助遍历【说明至少有一个小孩】
	curBoy := first
	for {
		fmt.Printf("小孩编号=%d ->", curBoy.No)
		// 退出的条件?curBoy.Next == first
		if curBoy.Next == first { // 到头了
			break
		}
		// curBoy移动到下一个
		curBoy = curBoy.Next
	}
}

func PlayGame(first *Boy, startNo int, countNum int) {
	// 1、空的链表，需要处理
	if first.Next == nil {
		fmt.Println("空的链表，没有小孩...")
		return
	}

	// 2、定义一个辅助节点，帮助我们删除小孩
	tail := first
	// 3、先让tail移动到环形链表的最后，这个非常重要
	for {
		if tail.Next == first {
			break
		}
		tail = tail.Next
	}
	// 4、先移动到开始的位置，让first移动到 startNo【后面删除小孩，就以first为准】
	for i := 1; i <= startNo-1; i++ {
		first = first.Next
		tail = tail.Next
	}
	fmt.Println()
	// 5、开始数countNum，然后就删除first 指向的小孩
	for {
		for i := 1; i <= countNum-1; i++ {
			first = first.Next
			tail = tail.Next
		}
		fmt.Printf("删除的小时是：%d\n", first.No)
		// 执行删除操作
		first = first.Next
		tail.Next = first

		// 判断如果 tail = first 圈子中只有一个小孩了
		if first == tail {
			break
		}
	}
	fmt.Printf("删除的小时是：%d\n", first.No)
}

/**
func TestJosephu(t *testing.T) {
	first := AddBody(5)
	// 显示
	ShowBoy(first)
}
**/

func TestJosephu() {
	first := AddBody(5)
	// 显示
	ShowBoy(first)

	PlayGame(first, 2, 3)
}
